#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
        vector<vector<int>> imox = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
        int slidingPuzzle(vector<vector<int>>& board) {
            //得到交换后的集合
            auto getnext = [&](string tmp)
            {
                int x = tmp.find('0');
                vector<string> res;
                for(auto y : imox[x])
                {
                    swap(tmp[x],tmp[y]);
                    res.emplace_back(tmp);
                    swap(tmp[x],tmp[y]);
                }
                return res;
            };
            string tmp;
            for(int i = 0; i < board.size(); i ++)
            {
                for(int j = 0; j < board[i].size(); j ++)
                {
                    tmp.push_back(board[i][j] +'0');
                }
            }
            queue<pair<string,int>> q;
            q.emplace(tmp,0);

            if(tmp == "123450")
            {
                return 0;
            }
            set<string> st;
            while(q.size())
            {
                auto [s,cnt] = q.front();
                q.pop();
                for(auto &x : getnext(s))
                {
                    if(st.find(x) == st.end())
                    {
                        if(x == "123450")
                        {
                            return cnt + 1;
                        }
                        q.emplace(x,cnt + 1);
                        st.insert(move(x));
                    }
                }
            }
            return -1;
        }
    };